import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public String modifyString(String s) {
        char[] ss=s.toCharArray();
        int len=ss.length;
        for(int i=0;i<len;i++){
            if(ss[i]=='?'){
                for(char j='a';j<='c';++j){
                    if((i==0||j!=ss[i-1])&&(i==len-1||ss[i+1]!=j)){
                        ss[i]=j;
                    }
                }
            }
        }
        return new String(ss);
    }
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret=0;
        for(int i=1;i<timeSeries.length;i++){
            int x=timeSeries[i]-timeSeries[i-1];
            if(x>=duration) ret+=duration;
            else ret+=x;
        }
        return ret+=duration;
    }
    public String convert(String s, int numRows) {
        if(s.length()==1||numRows>=s.length()||numRows==1){
            return s;
        }
        StringBuilder ret=new StringBuilder();
        int n=s.length();
        int d=numRows*2-2;
        for(int i=0;i<n;i+=d){
            ret.append(s.charAt(i));
        }
        for(int i=1;i<numRows-1;i++){
            for(int j=i,k=d-j;j<n||k<n;j+=d,k+=d){
                if(j<n) ret.append(s.charAt(j));
                if(k<n) ret.append(s.charAt(k));
            }
        }
        for(int i=numRows-1;i<n;i+=d){
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }
    public String countAndSay(int n) {
        String ret="1";
        for(int i=1;i<n;i++){
            StringBuilder str=new StringBuilder();
            for(int left=0,right=0;right<ret.length();){
                char x=ret.charAt(left);
                while(right<ret.length()&&ret.charAt(right)==x){
                    right++;
                }
                str.append(Integer.toString(right-left));
                str.append(x);
                left=right;
            }
            ret=str.toString();
        }
        return ret;
    }
    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] arr=croakOfFrogs.toCharArray();
        String s="croak";
        int n=s.length();
        int[] hash=new int[n];
        Map<Character,Integer> hashMap=new HashMap<>();
        for(int i=0;i<n;i++){
            hashMap.put(s.charAt(i),i);
        }
        for(char x:arr){
            if(x==s.charAt(0)){
                if(hash[n-1]!=0) hash[n-1]--;
                hash[0]++;
            }
            else{
                int i=hashMap.get(x);
                if(hash[i-1]!=0){
                    hash[i-1]--;
                    hash[i]++;
                }
                else return -1;
            }
        }
        for(int i=0;i<n-1;i++){
            if(hash[i]!=0) return -1;
        }
        return hash[n-1];
    }
}